package com.ryujung.dp.leetCode_85;

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;

/*
 * @lc app=leetcode.cn id=85 lang=java
 *
 * [85] 最大矩形
 *
 * https://leetcode-cn.com/problems/maximal-rectangle/description/
 *
 * algorithms
 * Hard (45.62%)
 * Likes:    405
 * Dislikes: 0
 * Total Accepted:    26.2K
 * Total Submissions: 57.2K
 * Testcase Example:  '[["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]'
 *
 * 给定一个仅包含 0 和 1 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。
 * 
 * 示例:
 * 
 * 输入:
 * [
 * ⁠ ["1","0","1","0","0"],
 * ⁠ ["1","0","1","1","1"],
 * ⁠ ["1","1","1","1","1"],
 * ⁠ ["1","0","0","1","0"]
 * ]
 * 输出: 6
 * 
 */

// @lc code=start
class Solution {
    /**
     * 动态规划:
     * 创建数组dp[i][j]代表在数组大小为matrix[i-1][j-1]范围内的最大矩形面积
     * 根据边界条件,即i=0或j=0,初始化dp
     */
    public int maximalRectangleDemo(char[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        if (m < 1 || n < 1) {
            return 0;
        }
        int[][] dp = new int[m][n];

        int maxArea = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {

            }
        }
        return 0;
    }

    /**
     * 个人想法：
     * 1. 可以根据84题，将问题拆解为，计算当前行为底的情况下，可求得的最大面积，然后逐行推算（中间部分行可以根据特征优化）
     * 2. 遍历平面所有的点，以当前点作为左上角，寻找右下方法的可能的最大面积
     * 3.
     * 
     */
    public static int maximalRectangle(char[][] matrix) {
        int maxArea = 0;
        if (matrix.length < 1) {
            return 0;
        }

        int[] heights = new int[matrix[0].length];
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                heights[j] = matrix[i][j] == '1' ? heights[j] + 1 : 0;
            }
            maxArea = Math.max(maxArea, largestRectangleArea(heights));
        }

        return maxArea;
    }

    public static int largestRectangleArea(int[] heights) {
        int max = 0;
        Deque<Integer> stack = new ArrayDeque<Integer>();

        int len = heights.length;
        int[] left = new int[len];
        int[] right = new int[len];
        for (int i = 0; i < len; i++) {
            while (!stack.isEmpty() && heights[stack.peek()] > heights[i]) {
                right[stack.pop()] = i;
            }
            left[i] = stack.isEmpty() ? -1 : stack.peek();
            stack.push(i);
        }
        stack.forEach(i -> right[i] = len);
        for (int i = 0; i < len; i++) {
            max = Math.max(max, heights[i] * (right[i] - left[i] - 1));
        }

        return max;
    }

    public static void main(String[] args) {
        // int[] heights = { 2, 1, 5, 6, 2, 3 };
        int[] heights = { 6, 7, 5, 2, 4, 5, 9, 3 };
        // int[] heights = { 1 };
        // int[] heights = { 1, 2, 1 };
        // int[] heights = { 1, 1 };
        // System.out.println(s.largestRectangleArea(heights));
        System.out.println(largestRectangleArea(heights));
    }

}
// @lc code=end
